Many methods for classifying and routing packets in communication systems are known in the art. In Internet packet classification systems, rules tables are used to classify and route incoming packets. An Internet router classifies incoming packets into flows utilizing information contained in packet headers and a table of classification rules, or rule or router table. Typically, packet classification is performed using only the destination address of a packet. Each rule-table rule is a pair of the form (F,A) where F is a filter and A is an action. The action component of a rule specifies what is to be done when a packet that satisfies the rule filter is received. Sample actions may include: drop the packet; forward the packet along a certain output link; and reserve a specified amount of bandwidth.
In typical Internet systems, each rule filter is a range [u,v] of destination addresses. A filter matches the destination address d if and only if u≦d≦v. Since an Internet rule-table may contain several rules that match a given destination address d, a tiebreaker is used to select a rule from the set of rules that match d. For purposes of this tiebreaker, each rule is assigned a priority, and the highest-priority rule that matched d determines the action for all packets whose destination address is d. Rule tables commonly include filters that specify ranges, wherein the highest-priority matching filter is used as highest-priority range-tables (HPRT). When the filters of no two rules of an HPRT intersect, the HPRT is a nonintersecting HPRT (NHPRT).
In a static rule table, the rule does not vary in time. For static rule tables, it is important to minimize the time required to process an incoming packet by searching, or looking up, the rule table for the rule to use. In addition, the processing time required to create the rule-table data structure needs to be minimized. Further, the storage requirements of the rule table structure need to be reduced to allow efficient operation. In practice, rule tables are seldom truly static. At best, rules may be added to or deleted from the rule table infrequently. Typically, in a static rule table, inserts/deletes are batched and rule-table data structure is reconstructed as needed.
In a dynamic rule table, rules are added/deleted with some frequency. For such tables, inserts/deletes are not batched. Rather, they are performed in real time. For such tables, the time required to insert/delete a rule is a concern. For a dynamic rule table, the initial rule-table data structure is constructed by starting with an empty data structure and then inserting the initial set of rules into the data structure one by one. Consequently, in the case of dynamic tables, the preprocessing metric, mentioned above, is very closely related to the insert time.
Data structures for rule tables in which each filter is a destination address prefix and the rule priority is the length of this prefix, or longest-matching prefix-tables (LMPT), have been intensely researched in recent years. Although every LMPT is also an NHPRT, an NHPRT may not be an LMPT.
Ruiz-Sanchez et al. (“Survey and Taxonomy of IP address lookup algorithms,” IEEE Network, 8-23 (2001)) review data structures for static LMPTs and Sahni et al. (“Data structures for one-dimensional packet classification using most-specific-rule matching,” International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN) (2002)) review data structures for both static and dynamic LMPTs. Several tree-based, or “trie”-based, data structures for LMPTs have been proposed (see Sklower, K., “A tree-based routing table for Berkeley Unix,” Technical Report, University of California, Berkeley (1993); Degermark et al., “Small forwarding tables for fast routing lookups,” ACM SIGCOMM, 3-14 (1997); Doeringer et al., “Routing on longest-matching prefixes,” IEEE/ACM Transactions on Networking, 4(1):86-97 (1996); Nilsson, S. and G. Karlsson, “Fast address look-up for Internet routers,” IEEE Broadband Communications (1998); Srinivasan, V. and G. Varghese, “Faster IP lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, 1-40 (1999); Sahni S. and K. Kim, “Efficient construction of fixed-Stride multibit tries for IP lookup,” Proceedings 8th IEEE Workshop on Future Trends of Distributed Computing Systems (2001); and Sahni, S. and K. Kim, “Efficient construction of variable-stride multibit tries for IP lookup,” Proceedings IEEE Symposium on Applications and the Internet (SAINT), 220-227 (2002)).
Structures such as that proposed by Sklower (Technical Report, University of California, Berkeley (1993)) perform each of the dynamic router-table operations (lookup, insert, delete) in O(W) time. W is commonly used to denote the maximum possible length of a prefix. In IPv4, W=32 and in IPv2, W=128.
Others (i.e., Degermark et al., ACM SIGCOMM, 3-14 (1997); Doeringer et al., IEEE/ACM Transactions on Networking 4(1):86-97 (1996); Nilsson, S. and G. Karlsson, IEEE Broadband Communications (1998); Srinivasan, V. and G. Varghese, ACM Transactions on Computer Systems (1999); Sahni, S. and K. Kim, Proceedings 8th IEEE Workshop on Future Trends of Distributed Computing Systems (2001); and Sahni, S. and K. Kim, Proceedings IEEE Symposium on Applications and the Internet (SAINT) (2002)) attempt to optimize lookup time and memory requirement through an expensive preprocessing step. These structures, while providing very fast lookup capability, have a prohibitive insert/delete time and so, they are suitable only for static router-tables (i.e., tables into/from which no inserts and deletes occur).
Waldvogel et al. (“Scalable high speed IP routing lookups,” ACM SIGCOMM, 25-36 (1997)) have proposed a scheme that performs a binary search on hash tables organized by prefix length. This binary search scheme has an expected complexity of O(log W) for lookup. An alternative adaptation of binary search to longest-prefix matching was developed by Lampson et al. (“IP lookup using multi-way and multicolumn search,” IEEE INFOCOM 98 (1998)). Using this adaptation, a lookup in a table that has n prefixes takes O(W+logn)=O(W) time. Because the schemes of Lampson et al. (as well as those of Waldvogel et al.) use expensive pre-computation, they are not suited for dynamic router tables.
Suri et al. (“Multiway range trees: Scalable IP lookup with fast updates,” GLOBECOM (2001) have proposed a B-tree data structure for dynamic LMPTs. Using their structure, the longest matching-prefix, LMP(d), may be found in O(logn) time. However, inserts/deletes take O(W logn) time. When W bits fit in O(1) words (as is the case for IPv2 and IPv6 prefixes) logical operations on W-bit vectors can be done in O(1) time each. In this case, the scheme of Suri et al. takes O(W+logn)=O(W) time for an update. The number of cache misses that occur when the data structure of [19] is used is O(logn) per operation.
Sahni and Kim (see “O(logn) dynamic packet routing,” IEEE Symposium on Computers and Communications (2002)) have developed data structures called a collection of red-black trees (CRBT) and alternative collection of red-black trees (ACRBT) that support the three operations of a dynamic LMPT in O(logn) time each. The number of cache misses is also O(logn).
When an HPPT (highest-priority prefix-table) is represented as a binary trie (See Horowitz et al., Fundamentals of Data Structures in C++, W. H. Freeman, NY, 653 pages (1995)), each of the three dynamic HBRT operations takes O(W) time and cache misses. Gupta and McKeown (“Dynamic algorithms with worst-case performance for packet classification,” IFIP Networking (2000)) have developed two data structures for dynamic HRPTs-heap on trie (HOT) and binary search trie on tree (BOT). The HOT structures take O(W) time for a lookup and O(W logn) time for an insert or delete. The BOT structure takes O(W logn) time for a lookup and O(W) time for an insert/delete. The number of cache misses in a HOT and BOT is asymptotically the same as the time complexity of the corresponding operation. However it would be desirable to reduce these times as much as possible to efficiently route packets.
In addition to the above mentioned papers, a number of U.S. patents and published applications address dynamic routing schemes including, but not limited to U.S. Pat. Nos. 6,341,130; 6,335,932; 6,289,013; 6,212,184; 6,157,955; 6,092,072; 6,061,712; 6,041,053; 6,021,131; 6,018,524; 5,909,440; 5,787,430; 5,701,467; 5,555,405; 4,833,468; 4,251,861; each of which is incorporated herein by reference.
Accordingly, there is a need in the art for a dynamic data table routing structure to provide more effective ways to classify and route data packets for NHPRT's, HPPT's, and LMPT's. Specifically, the structure needs to provide a quicker and more memory efficient method to search, insert and delete items in a dynamic router data table.